package com.yx.study.leet.questionList.questions;

import com.yx.study.leet.utils.ListNode;
import org.junit.Test;

/**
 * 23. 合并 K 个升序链表
 * https://leetcode.cn/problems/merge-k-sorted-lists/
 * */
public class MergeKLists23 {
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        while (true) {
            ListNode minNode = null;
            int minPointer = -1;
            for (int i = 0; i < k; i++) {
                if (lists[i] == null) {
                    continue;
                }
                if (minNode == null || lists[i].val < minNode.val) {
                    minNode = lists[i];
                    minPointer = i;
                }
            }
            if (minPointer == -1) {
                break;
            }
            tail.next = minNode;
            tail = tail.next;
            lists[minPointer] = lists[minPointer].next; // 删除已合并的节点
        }
        return dummyHead.next;
    }

    @Test
    public void test() {
        // [[1, 4, 5],[1, 3, 4],[2, 6]]
        ListNode listNode = new ListNode(1, new ListNode(4, new ListNode(5)));
        ListNode listNode2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode listNode3 = new ListNode(2, new ListNode(6));
        ListNode[] lists = new ListNode[]{listNode, listNode2, listNode3};
        System.out.println(mergeKLists(lists).toString());
    }
}
